Winter math
This crate contains modules with mathematical operations needed in STARK proof generation and verification.
Finite field
Finite field module implements arithmetic operations in STARK-friendly finite fields. The operation include:
- Basic arithmetic operations: addition, multiplication, subtraction, division, inversion.
- Drawing random and pseudo-random elements from the field.
- Computing roots of unity of a given order.
Currently, there are two implementations of finite fields:
- A 128-bit field with modulus 2128 - 45 * 240 + 1. This field was not chosen with any significant thought given to performance, and the implementation of most operations is sub-optimal as well. Proofs generated in this field can support security level of ~100 bits. If higher level of security is desired, proofs must be generated in a quadratic extension of the field.
- A 62-bit field with modulus 262 - 111 * 239 + 1. This field supports very fast modular arithmetic including branchless multiplication and addition. To achieve adequate security (i.e. ~100 bits), proofs must be generated in a quadratic extension of this field. For higher levels of security, a cubic extension field should be used.
Extension fields
Currently, the library provides a generic way to create quadratic extensions of STARK fields. An extension element is defined as α + β * φ, where φ is a root of the polynomial x2 - x - 1, and α and β are base field elements.
Support for cubic extension fields is not yet available.
Polynomials
Polynomials module implements basic polynomial operations such as:
- Evaluation of a polynomial at a single point.
- Interpolation of a polynomial from a set of points (using Lagrange interpolation).
- Addition, multiplication, subtraction, and division of polynomials.
- Synthetic polynomial division (using Ruffini's method).
Fast Fourier transform
FFT module contains operations for computing Fast Fourier transform in a prime field (also called Number-theoretic transform). This can be used to interpolate and evaluate polynomials in O(n log n) time as long as the domain of the polynomial is a multiplicative subgroup with size which is a power of 2.
Crate features
This crate can be compiled with the following features:
std
- enabled by default and relies on the Rust standard library.concurrent
- impliesstd
and also enables multi-threaded execution for some of the crate functions.no_std
- does not rely on Rust's standard library and enables compilation to WebAssembly.
To compile with no_std
, disable default features via --no-default-features
flag.
Concurrent execution
When compiled with concurrent
feature enabled, the following operations will be executed in multiple threads:
- fft module:
evaluate_poly()
evaluate_poly_with_offset()
interpolate_poly()
interpolate_poly_with_offset()
get_twiddles()
get_inv_twiddles()
- utils module:
get_power_series()
get_power_series_with_offset()
add_in_place()
mul_acc()
batch_inversion()
The number of threads can be configured via RAYON_NUM_THREADS
environment variable, and usually defaults to the number of logical cores on the machine.
License
This project is MIT licensed.